package frist50;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Stack;

public class T0032 {
    public int longestValidParentheses(String s) {
        int len = s.length();
        if (len == 0) return 0;
        int[] arr = new int[len];
        arr[0] = 0;
        for (int i = 1; i < len; i++) {
            if (s.charAt(i) == ')' && i - arr[i - 1] - 1 >= 0 && s.charAt(i - arr[i - 1] - 1) == '(') {
                if (i - arr[i - 1] - 2 >= 0) {
                    arr[i] = arr[i - 1] + arr[i - arr[i - 1] - 2] + 2;
                } else {
                    arr[i] = arr[i - 1] + 2;
                }
            } else {
                arr[i] = 0;
            }
        }
        int max = 0;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }

    public int longestValidParentheses2(String s) {
        int len = s.length();
        if (len == 0) return 0;
        int max=0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < len; i++) {
            if (s.charAt(i)=='('){
                stack.push(i);
            }else {
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else {
                    max=Math.max(max,i-stack.peek());
                }
            }
        }
        return max;
    }


    @Test
    public void test() {
        System.out.println(longestValidParentheses2("))))((()(("));
    }
}
